package Game;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.stream.Collectors;

public class ShanDuoLa {

	/**
	 * 按钮移动方向枚举
	 */
	private enum BtnDirect {
		UP, DOWN, LEFT, RIGHT
	}

	/**
	 * 地图: 0 空位置 1 可踩按钮 2 不可踩按钮 3 跳板
	 */
	private int[][] matrix = {
			{ 1, 0, 1, 3, 2 },
			{ 0, 0, 3, 0, 0 },
			{ 1, 0, 1, 0, 1 },
			{ 0, 0, 3, 0, 0 },
			{ 1, 3, 1, 0, 1 } };

	/**
	 * 按钮及其移动方向
	 */
	private Map<String, BtnDirect> button = new HashMap<>();

	/**
	 * 8个按钮的踩踏顺序
	 */
	private Stack<String> seq = new Stack<String>();

	public ShanDuoLa() {
		button.put("0,0", BtnDirect.UP);
		button.put("0,2", BtnDirect.UP);
		button.put("2,0", BtnDirect.RIGHT);
		button.put("2,2", BtnDirect.DOWN);
		button.put("2,4", BtnDirect.DOWN);
		button.put("4,0", BtnDirect.LEFT);
		button.put("4,2", BtnDirect.RIGHT);
		button.put("4,4", BtnDirect.LEFT);
	}

	/**
	 * 子串转数组
	 */
	private int[] str2arr(String pos) {
		return Arrays.stream(pos.split(",")).mapToInt(Integer::valueOf).toArray();
	}

	/**
	 * 数组转字符串
	 */
	private String arr2str(int[] arr) {
		return arr[0] + "," + arr[1];
	}

	/**
	 * 数组转字符串
	 */
	private String arr2str(int row, int col) {
		return row + "," + col;
	}

	/**
	 * 当前位置是否为可踩按钮
	 */
	private boolean isValidBtn(String pos) {
		int[] arr = str2arr(pos);
		return isValidBtn(arr);
	}

	/**
	 * 当前位置是否为可踩按钮
	 */
	private boolean isValidBtn(int[] pos) {
		return matrix[pos[0]][pos[1]] == 1;
	}

	/**
	 * 获取地图中所有按钮位置
	 */
	private List<String> getBoards() {
		List<String> res = new ArrayList<String>();
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix.length; j++) {
				if (matrix[i][j] == 3) {
					res.add(arr2str(i, j));
				}
			}
		}
		return res;
	}

	/**
	 * 广搜获取当前位置可达的所有非0位置
	 * 
	 * @param pos 当前位置
	 * @return 非0位置列表
	 */
	private Set<String> getAccessPos(int[] pos) {
		String curPos = arr2str(pos);
		Queue<String> queue = new LinkedList<String>();
		Set<String> visited = new HashSet<String>();
		queue.offer(curPos);
		visited.add(curPos);
		while (!queue.isEmpty()) {
			int[] temp = str2arr(queue.poll());
			if (temp[0] > 0 && matrix[temp[0] - 1][temp[1]] != 0) {
				String upPos = arr2str(temp[0] - 1, temp[1]);
				if (!visited.contains(upPos)) {
					queue.offer(upPos);
					visited.add(upPos);
				}
			}
			if (temp[0] < matrix.length - 1 && matrix[temp[0] + 1][temp[1]] != 0) {
				String downPos = arr2str(temp[0] + 1, temp[1]);
				if (!visited.contains(downPos)) {
					queue.offer(downPos);
					visited.add(downPos);
				}
			}
			if (temp[1] > 0 && matrix[temp[0]][temp[1] - 1] != 0) {
				String leftPos = arr2str(temp[0], temp[1] - 1);
				if (!visited.contains(leftPos)) {
					queue.offer(leftPos);
					visited.add(leftPos);
				}
			}
			if (temp[1] < matrix[0].length - 1 && matrix[temp[0]][temp[1] + 1] != 0) {
				String rightPos = arr2str(temp[0], temp[1] + 1);
				if (!visited.contains(rightPos)) {
					queue.offer(rightPos);
					visited.add(rightPos);
				}
			}
		}
		return visited;
	}

	/**
	 * 从所有可达位置中筛选出所有可踩按钮
	 * 
	 * @param pos 当前位置
	 * @return 可踩按钮列表
	 */
	private Set<String> getAccessBtns(int[] pos) {
		Set<String> res = new HashSet<String>();
		Set<String> accessPos = getAccessPos(pos);
		for (String str : accessPos) {
			if (isValidBtn(str)) {
				res.add(str);
			}
		}
		return res;
	}

	/**
	 * @return 复制一个地图
	 */
	private int[][] copyMatrix() {
		int[][] copy = new int[matrix.length][matrix[0].length];
		for (int i = 0; i < copy.length; i++) {
			for (int j = 0; j < copy[0].length; j++) {
				copy[i][j] = matrix[i][j];
			}
		}
		return copy;
	}

	/**
	 * 游戏是否结束
	 */
	private boolean gameover() {
		// 地图中没有1了就是结束了
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				if (matrix[i][j] == 1) {
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * 踩按钮，按钮失效，踏板移动
	 * 
	 * @param pos 当前位置
	 */
	private void clickBtn(int[] pos) {
		String curPos = arr2str(pos);
		// 所有踏板位置
		List<String> boards = getBoards();
		if (matrix[pos[0]][pos[1]] != 1 || !button.containsKey(curPos)) {
			return;
		}
		// 点击按钮会使踏板失效
		matrix[pos[0]][pos[1]] = 2;
		BtnDirect dir = button.get(curPos);
		// 点击按钮会使踏板移动
		switch (dir) {
		case UP:
			for (String boardPos : boards) {
				int[] temp = str2arr(boardPos);
				if (temp[0] > 1 && matrix[temp[0] - 1][temp[1]] == 0 && matrix[temp[0] - 2][temp[1]] == 0) {
					matrix[temp[0]][temp[1]] = 0;
					matrix[temp[0] - 2][temp[1]] = 3;
				}
			}
			break;
		case DOWN:
			for (String boardPos : boards) {
				int[] temp = str2arr(boardPos);
				if (temp[0] < matrix.length - 2 && matrix[temp[0] + 1][temp[1]] == 0
						&& matrix[temp[0] + 2][temp[1]] == 0) {
					matrix[temp[0]][temp[1]] = 0;
					matrix[temp[0] + 2][temp[1]] = 3;
				}
			}
			break;
		case LEFT:
			for (String boardPos : boards) {
				int[] temp = str2arr(boardPos);
				if (temp[1] > 1 && matrix[temp[0]][temp[1] - 1] == 0 && matrix[temp[0]][temp[1] - 2] == 0) {
					matrix[temp[0]][temp[1]] = 0;
					matrix[temp[0]][temp[1] - 2] = 3;
				}
			}
			break;
		case RIGHT:
			for (String boardPos : boards) {
				int[] temp = str2arr(boardPos);
				if (temp[1] < matrix[0].length - 2 && matrix[temp[0]][temp[1] + 1] == 0
						&& matrix[temp[0]][temp[1] + 2] == 0) {
					matrix[temp[0]][temp[1]] = 0;
					matrix[temp[0]][temp[1] + 2] = 3;
				}
			}
			break;
		}
	}

	/**
	 * 当前位置是否有解，有解的话打印出来
	 * 
	 * @param pos 当前位置
	 * @return 是否有解
	 */
	public boolean canSolve(int[] pos) {
		int[][] matrixCopy = copyMatrix();
		// 按钮全部踩过，游戏结束
		if (gameover()) {
			String res = new ArrayList<String>(seq).stream().collect(Collectors.joining(" -> "));
			System.out.println(res);
			return true;
		}
		Set<String> accessBtns = getAccessBtns(pos);
		// 按钮没踩完但是已经没有可达的有效按钮了，失败
		if (accessBtns.size() == 0) {
			return false;
		}
		for (String str : accessBtns) {
			int[] btnPos = str2arr(str);
			// 踩按钮
			clickBtn(btnPos);
			seq.push(str);
			if (canSolve(btnPos)) {
				return true;
			}
			// 恢复地图
			matrix = matrixCopy;
			seq.pop();
		}
		return false;
	}

	public static void main(String[] args) {
		ShanDuoLa shanduola = new ShanDuoLa();
		System.out.println(shanduola.canSolve(new int[] { 0, 4 }));
	}
}
